/**
 * 221. 最大正方形
 * https://leetcode-cn.com/problems/maximal-square/
 */

// let stack;
// let top;
// let lowersLeft;
// let lowersRight;
//
// /**
//  * @param {number[]} heights
//  * @return {number}
//  */
// function maxArea(heights) {
//   top = -1;
//   for (let i = 0; i < heights.length; i += 1) {
//     while (top >= 0 && heights[i] <= heights[stack[top]]) {
//       top -= 1;
//     }
//     lowersLeft[i] = top >= 0 ? stack[top] : -1;
//     top += 1;
//     stack[top] = i;
//   }
//   top = -1;
//   for (let i = heights.length - 1; i >= 0; i -= 1) {
//     while (top >= 0 && heights[i] <= heights[stack[top]]) {
//       top -= 1;
//     }
//     lowersRight[i] = top >= 0 ? stack[top] : heights.length;
//     top += 1;
//     stack[top] = i;
//   }
//   let max = 0;
//   for (let i = 0; i < heights.length; i += 1) {
//     const area = Math.min(heights[i], lowersRight[i] - lowersLeft[i] - 1) ** 2;
//     if (area > max) {
//       max = area;
//     }
//   }
//   return max;
// }
//
// /**
//  * @param {string[][]} matrix
//  * @return {number}
//  */
// function maximalSquare(matrix) {
//   stack = new Array(matrix[0].length).fill(0);
//   lowersLeft = Array.from(stack);
//   lowersRight = Array.from(stack);
//   const heights = Array.from(stack);
//   let max = 0;
//   for (let i = 0; i < matrix.length; i += 1) {
//     const row = matrix[i];
//     for (let j = 0; j < row.length; j += 1) {
//       if (row[j] === '1') {
//         heights[j] += 1;
//       } else {
//         heights[j] = 0;
//       }
//     }
//     max = Math.max(max, maxArea(heights));
//   }
//   return max;
// }

/**
 * @param {string[][]} matrix
 * @return {number}
 */
function maximalSquare(matrix) {
  const { length: n } = matrix;
  const { length: m } = matrix[0];
  const dp = new Array(n);
  for (let i = 0; i < n; i += 1) {
    dp[i] = new Array(m).fill(0);
  }
  let maxSize = 0;
  for (let i = 0; i < n; i += 1) {
    if (matrix[i][0] === '1') {
      dp[i][0] = 1;
      maxSize = 1;
    }
  }
  for (let j = 1; j < m; j += 1) {
    if (matrix[0][j] === '1') {
      dp[0][j] = 1;
      maxSize = 1;
    }
  }
  for (let i = 1; i < n; i += 1) {
    for (let j = 1; j < m; j += 1) {
      if (matrix[i][j] === '1') {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
        maxSize = Math.max(maxSize, dp[i][j]);
      }
    }
  }
  return maxSize * maxSize;
}

console.log(maximalSquare([
  ['1', '0', '1', '0', '0'],
  ['1', '0', '1', '1', '1'],
  ['1', '1', '1', '1', '1'],
  ['1', '0', '0', '1', '0'],
]) === 4);
console.log(maximalSquare([
  ['0', '1'],
  ['1', '0'],
]) === 1);
console.log(maximalSquare([
  ['0'],
]) === 0);
